package com.zjsru.plan2025.oneday;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 3170. 删除星号以后字典序最小的字符串
 *
 * @Author: cookLee
 * @Date: 2025-06-07
 */
public class ClearStars {

    /**
     * 主
     * \
     * 输入：s = "aaba*"
     * 输出："aab"
     * 解释：
     * 删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ，s 字典序最小。
     * \
     * 输入：s = "abc"
     * 输出："abc"
     * 解释：
     * 字符串中没有 '*' 字符。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        ClearStars clearStars = new ClearStars();
        System.out.println(clearStars.clearStars("aaba*"));
    }

    public String clearStars(String s) {
        Deque<Integer>[] deques = new Deque[26];
        for (int i = 0; i < 26; i++) {
            deques[i] = new ArrayDeque<>();
        }
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (s.charAt(i) == '*') {
                for (int j = 0; j < 26; j++) {
                    if (!deques[j].isEmpty()) {
                        //移除栈顶元素
                        Integer pop = deques[j].pop();
                        //替换chars被移除的元素后置为*，后续过滤
                        chars[pop] = '*';
                        break;
                    }
                }
            } else {
                deques[chars[i] - 'a'].push(i);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (char aChar : chars) {
            if (aChar != '*') {
                sb.append(aChar);
            }
        }
        return sb.toString();
    }

}
